The invention relates to configuring a five gate logic cell and a tree circuit configuration utilizing the logic cells as nodes in the tree to establish a lookahead synchronization circuit for parallel processors.
A significant problem encountered in parallel processing is the difficulty in efficiently controlling the activities of the multiple processing elements. Specialized circuits have been designed to implement a variety of primitive synchronization functions including fetch-and-op, priority, and other primitives. Fetch-and-op allows simultaneous reads and writes to a memory and includes, for example, fetch-and-add, fetch-and-AND, fetch-and-OR, and fetch-and-exclusive-OR. By way of illustration, the fetch-and-add primitive implements the sequence of indivisible operations of: 1) fetching the variable to be operated on; 2) adding the desired value to the variable; and, 3) returning the new value of the variable. Conventional methods of implementing these primitives in a parallel computing environment have been known to require in excess of 10,000 gates per node in a network.
High costs associated with complex synchronization circuits increase both the costs and the complexity of the parallel computers in which they reside. Further, the increased costs and increased complexity can result in high costs per processing element in a parallel computing environment.
The complexity of the synchronization circuit is further increased when additional primitives are required. Therefore, a less complex synchronization circuit utilizing fewer gates would significantly reduce the costs of a parallel computer. Further, fewer gates in a circuit will reduce delays associated with signals traversing the synchronization circuit.
A single circuit capable of implementing multiple primitives will further reduce circuit complexity, further reduce delays due to throughput in the synchronization circuit and can reduce costs of parallel computers.